home *** CD-ROM | disk | FTP | other *** search
- Path: hubcap.clemson.edu!hubcap!mjs
- From: mjs@hubcap.clemson.edu (M. J. Saltzman)
- Newsgroups: comp.std.c
- Subject: Re: Restrictions on qsort compare function?
- Date: 21 Mar 96 14:53:18 GMT
- Organization: Clemson University
- Message-ID: <mjs.827419998@hubcap>
- References: <4iokop$h4p@lyra.csx.cam.ac.uk>
- NNTP-Posting-Host: hubcap.clemson.edu
- X-Newsreader: NN version 6.5.0 #1
-
- jkb@mrc-lmb.cam.ac.uk (James Bonfield) writes:
-
- |Are there any limitations on what the sort function passed over to qsort can
- |do or return? I know it's meant to return < 0, 0 or > 0 for the various
- |compare operations, but which you return is purely up to your own comparison
- |system.
-
- |On tracking down a bug in some old code I noticed that we had the
- |compare function returning something like "a > b" instead of "b - a".
- |Now this is obviously some silly bug in our coding, but "a > b" is still
- |a valid sort function surely? The reason I ask is that this that such
- |functions appear to make the Irix 5.3 qsort() function underflow the
- |passed array. Please check the following function to verify that I
- |haven't done something daft.
-
- As others have pointed out, b - a runs the risk of overflow if a and b
- are large enough in magnitude and of opposite sign. That's why it is
- often recommended against as a value to return from the compare function.
- BTW, without overflow, b - a is positive if b > a, not if a > b.
-
-
- |#include <stdio.h>
- |#include <stdlib.h>
-
- |static int sort_func(const void *pa, const void *pb)
- |{
- | const int *a = (int *)pa;
- | const int *b = (int *)pb;
-
- | return *a > *b;
- |}
-
- This function returns either a 0 if *a <= *b or a 1 if *a > *b. Since
- keys are considered equal if sort_func() returns zero, this will not
- properly discern a case where the first argument must appear before
- the second. It would surprise me not at all if qsort() relied on
- sort_func() having the property that
-
- !!sort_func(p1, p2) == -1 * !!sort_func(p2, p1)
-
- which does not hold for this function. (The Standard wording seems
- to me to require this property, but I'm not a duly certified language
- lawyer...)
-
- Try
-
- static int sort_func(const void *pa, const void *pb)
- {
- const int *a = (int *)pa;
- const int *b = (int *)pb;
-
- return (*a > *b) - (*a < *b);
- }
-
- instead.
- --
- Matthew Saltzman
- Clemson University Math Sciences
- mjs@clemson.edu
-